Large deviations for Markov chain Monte Carlo methods: the surprisingly curious case of Metropolis-Hastings.

Abstract: Markov chain Monte Carlo (MCMC) methods have become the workhorse for numerical computations in a range of scientific disciplines, e.g., computational chemistry and physics, statistics, and machine learning. The performance of MCMC methods has therefore become an important topic at the intersection of probability theory and (computational) statistics: e.g., when the underlying distribution one is trying to sample from becomes sufficiently complex, convergence speed and/or the cost per iteration becomes an issue for most MCMC methods.

The analysis, and subsequently design, of MCMC methods has to a large degree relied on classical tools used to determine the speed of convergence of Markov chains, e.g., mixing times, spectral gap and functional inequalities (Poincaré, log-Sobolev). An alternative avenue is to use the theory of large deviations for empirical measures. In this talk I will first give a general outline of this approach to analysing MCMC methods, along with some recent examples. I will then consider the specific case of the Metropolis-Hastings algorithm, the most classical amongst all MCMC methods and a foundational building block for many more advanced methods. Despite the simplicity of this method, it turns out that the theoretical analysis of it is still a rich area, and from the large deviation perspective it is surprisingly difficult to treat. As a first step we show a large deviation principle for the underlying Markov chain, extending the celebrated Donsker-Varadhan theory. Time permitted I will also discuss ongoing and future work on using this result for better understanding of both the Metropolis-Hastings method and more advanced methods, such as approximate Bayesian computation (ABC-MCMC) and the Metropolis-adjusted Langevin algorithm (MALA).

The talk will be self-contained and no prior knowledge of either MCMC methods or large deviations is required.

The talk is primarily based on join work with Federica Milinanni (KTH).

machine learningprobabilitystatistics theory

Audience: researchers in the discipline

Gothenburg statistics seminar

Series comments: Gothenburg statistics seminar is open to the interested public, everybody is welcome. It usually takes place in MVL14 (http://maps.chalmers.se/#05137ad7-4d34-45e2-9d14-7f970517e2b60, see specific talk). Speakers are asked to prepare material for 35 minutes excluding questions from the audience.